package com.leetcode.LeetCode精选TOP面试题;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-05-25 17:39
 */
public class 题库_0054_螺旋矩阵 {

  public static void main(String[] args) {
    int[][] matrix = {{1,2,3},{4,5,6},{7,8,9}};
    Solution solution = new Solution();
    List<Integer> integers = solution.spiralOrder(matrix);
    System.out.println(integers);
  }

  static
  class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
      if (matrix == null || matrix.length == 0) {
        return new ArrayList<>();
      }

      List<Integer> answers = new ArrayList<>();
      int si = 0;
      int sj = 0;
      int ei = matrix.length - 1;
      int ej = matrix[0].length - 1;

      Point point = new Point(si, sj, ei, ej, si, sj, 0);

      while (!point.isEnd) {
        answers.add(matrix[point.x][point.y]);
        point.next();
      }

      return answers;
    }

    static class Point {
      int si;
      int sj;
      int ei;
      int ej;
      int x;
      int y;
      boolean isEnd;
      /**
       * 0: 向右
       * 1: 向下
       * 2: 向左
       * 3: 向上
       */
      int direct;

      public Point(int si, int sj, int ei, int ej, int x, int y, int direct) {
        this.si = si;
        this.sj = sj;
        this.ei = ei;
        this.ej = ej;
        this.x = x;
        this.y = y;
        initDirect();
      }

      private void initDirect() {
        if (si < ei && sj == ej) {
          direct = 1;
        } else {
          direct = 0;
        }
      }

      public void next() {
        switch (direct) {
          case 0:
            ++y;
            // 转向下
            if (y == ej) {
              direct = 1;
            }
            break;
          case 1:
            ++x;
            // 转向左
            if (x == ei) {
              direct = 2;
            }
            break;
          case 2:
            --y;
            // 转向上
            if (y == sj) {
              direct = 3;
            }
            break;
          default:
            --x;
            // 边界内卷、转向右
            if (x == si) {
              ++si;
              ++sj;
              --ei;
              --ej;
              x = si;
              y = sj;
              initDirect();
            }
        }
        if (x < si || x > ei || y < sj || y > ej) {
          isEnd = true;
        }
      }
    }
  }

}
